﻿// 1-15.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
//比较两数大小，返回大者
int max(int a, int b) {
    if (a > b) return a;
    else return b;
}




//从n个元素中找出最大者
//复杂度O(n)
//递归
int searchMaxA(int* A, int size) {
    if (size == 1) return A[0];
    if (A[0] < A[size - 1]) {
        A[0] += A[size - 1];
        A[size - 1] = A[0] - A[size - 1];
        A[0] -= A[size-1];
    }
    searchMaxA(A, size - 1);
}

//从n个元素中找出最大者
//复杂度O（n）
//迭代
int searchMaxB(int* A, int size) {
    int max = A[0];
    while (1 < size) {
        if (max < A[size - 1]) max = A[size - 1];
        size--;
    }

    return max;
}

//从n个元素中找出最大者
//复杂度O（logn）!!!!!!!!!!（不对不对，课本的结论是，它的空间复杂度是O（logn），而时间复杂度应该还是O（n））
//二分递归
int searchMaxC(int A[], int lo, int hi) {  //计算数组区间A[lo,hi)的最大值
    if (lo + 1 == hi)
        return A[lo];
    else {
        int mi = (lo + hi) >> 1;
        return max(searchMaxC(A,lo, mi), searchMaxC(A,mi, hi));
    }

}

int main()
{
    int arr[] = { 1,20,3,4,5,6,70,8,9 };
    int a = searchMaxA(arr, sizeof(arr) / sizeof(arr[0]));
    int b = searchMaxB(arr, sizeof(arr)/sizeof(arr[0]));
    int c = searchMaxC(arr, 0, 9);
    std::cout <<a<< "\n";
    std::cout <<b<< "\n";
    std::cout <<c<< "\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
